#pragma once
#include <vector>
#include <iostream>
#include <functional>

#define v2_binary_search 1

#ifdef v1_bingary_search
int binary_search(std::vector<int>& a, int x)
{
    int l = 0, r = a.size()-1;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(a[mid] == x) return mid;
        else if(a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}
#elif v2_binary_search
//整数二分 -- 数组下标
int LeftBoard(std::vector<int>& a, int x)
{
    int l = -1, r = a.size();
    while(l+1 != r)
    {
        int mid = r+l >> 1;
        if(a[mid] < x) l = mid;
        else r = mid;
    }
    return r == a.size() || a[r] != x ? -1 : r;
}

int RightBoard(std::vector<int>& a, int x)
{
    int l = -1, r = a.size();
    while(l + 1 != r)
    {
        int mid = r + l >> 1;
        if(a[mid] > x) r = mid;
        else l = mid;
    }
    return l == -1 || a[l] != x ? -1 : l;
}
//浮点数 -- 求n次方根
double square_root(double x, int n)
{
    std::function<double(double, int)> Mul = [](double mid, int n)->double {
        double ret = 1;
        for(int i = 0; i < n; i++)
        {
            ret *= mid;
        }
        return ret;
    };
    double l = -10000, r = 10000;
    while(r-l > 1e-8) {
        double mid = (r+l) / 2;
        if(Mul(mid, n) < x) l = mid;
        else r = mid;
    }
    return l; //或r
}

#endif